package com.example.offer;

import com.alibaba.fastjson.JSON;

import java.util.*;

/**
 * @author wxz
 * 剑指 Offer 40. 最小的k个数（第k小）
 * 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
 * 示例 1：
 * <p>
 * 输入：arr = [3,2,1], k = 2
 * 输出：[1,2] 或者 [2,1]
 * <p>
 * 注意⚠️：不要求排序，只返回最小的这些数即可。
 * 所以会有思路，快排实际上提供了在轴心值两边不同的列表，我们可利用这个特点。
 * 即不进行完全的快速排序，而是进行一半，只需要目标范围和轴心值的下标相同即可。所以每次只需要排序半个列表。
 */
public class SmallestKNumber {

    public static void main(String[] args) {
        SmallestKNumber smallestKNumber = new SmallestKNumber();
        int[] arr = new int[]{7, 6, 5, 4, 3, 2, 1};
        System.out.println(JSON.toJSONString(smallestKNumber.getLeastNumbers(arr, 5)));
        smallestKNumber.getMaxtNumbers(arr, 2);
    }

    private static void quickSort(int[] n, int left, int right, int k) {
        if (left >= right) {
            return;
        }
        int i = left;
        int j = right;
        int key = n[left];
        //一次while循环完成一轮快速排序，最终确定切割点key的位置
        while (i < j) {
            while (i < j && n[j] >= key) {
                j--;
            }
            while (i < j && n[i] <= key) {
                i++;
            }
            //将n[i]>key,n[j]<key的进行替换
            if (i < j) {
                int temp = n[i];
                n[i] = n[j];
                n[j] = temp;
            }
        }
        //将n[i]赋给起始点，将key的值赋给它的最终位置i点
        n[left] = n[i];
        n[i] = key;
        //分别对切割点左右两个数组进行递归
        /**
         * 注意，真正的快排没有底下的if判断，而是两个递归都执行，
         * 但此题可根据此技巧减少大量的多余操作，节省时间
         * */
        if (i > k) {
            quickSort(n, left, i - 1, k);
        } else {
            quickSort(n, i + 1, right, k);
        }
    }

    public int[] getLeastNumbers(int[] arr, int k) {
        int left = 0, right = arr.length - 1;
        quickSort(arr, left, right, k);
        return Arrays.copyOf(arr, k);
    }

    public int[] getMaxtNumbers(int[] arr, int k) {
        int left = 0, right = arr.length - 1;
        quickSort(arr, left, right, right - k + 2);
        return Arrays.copyOf(arr, right - k);
    }

    /**
     * 347. 前 K 个高频元素
     * 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
     * <p>
     * 示例 1:
     * <p>
     * 输入: nums = [1,1,1,2,2,3], k = 2
     * 输出: [1,2]
     * 示例 2:
     * <p>
     * 输入: nums = [1], k = 1
     * 输出: [1]
     */
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>(nums.length);
        for (int i : nums) {
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        PriorityQueue<int[]> queue = new PriorityQueue<>(map.size(),(m, n) -> n[1] - m[1]);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            queue.add(new int[]{entry.getKey(), entry.getValue()});
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = Objects.requireNonNull(queue.poll())[0];
        }
        return res;
    }
}


/**
 * 剑指 Offer 41. 数据流中的中位数
 * 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
 * <p>
 * 例如，
 * <p>
 * [2,3,4] 的中位数是 3
 * <p>
 * [2,3] 的中位数是 (2 + 3) / 2 = 2.5
 * <p>
 * 设计一个支持以下两种操作的数据结构：
 * <p>
 * void addNum(int num) - 从数据流中添加一个整数到数据结构中。
 * double findMedian() - 返回目前所有元素的中位数。
 * 示例 1：
 * <p>
 * 输入：
 * ["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
 * [[],[1],[2],[],[3],[]]
 * 输出：[null,null,null,1.50000,null,2.00000]
 * <p>
 * <p>
 * PriorityQueue优先队列是一种类似堆的结构，维护队列中元素的顺序，
 * 可以通过new PriorityQueue<>(256,Comparator.naturalOrder())//new PriorityQueue<>(256)默认维护正序的队列  peek/poll是最小值
 * 可以通过new PriorityQueue<>(256, Comparator.reverseOrder());来创造反序的队列 peek/poll是最大值
 * 但是，只是poll出的值是有序的，实际存在数组中的值是无序的，存的顺序就像一棵树
 */
class MedianFinder {
    Queue<Integer> A, B;

    public MedianFinder() {
        A = new PriorityQueue<>(256); // 小顶堆，保存较大的一半
        B = new PriorityQueue<>(256, (x, y) -> (y - x)); // 大顶堆，保存较小的一半
        B = new PriorityQueue<>(256, Comparator.reverseOrder());
    }

    public static void main(String[] args) {
        PriorityQueue<Integer> integers = new PriorityQueue<>(256, Comparator.naturalOrder());// 小顶堆，保存较大的一半
        PriorityQueue<Integer> integers1 = new PriorityQueue<>(256, Comparator.reverseOrder());// 大顶堆，保存较小
        integers.add(1);
        integers.add(13);
        integers.add(142);
        integers.add(11);
        integers.add(15);

        integers1.add(1);
        integers1.add(13);
        integers1.add(12);
        integers1.add(142);
        integers1.add(11);
        integers1.add(15);
        System.out.println(integers1);
        System.out.println(integers1.poll());
        System.out.println(integers1.poll());
        System.out.println(integers1.poll());
        System.out.println(integers1.poll());
        System.out.println(integers1.poll());
        System.out.println(integers.peek());
        System.out.println(integers1.peek());
    }

    public void addNum(int num) {
        if (A.size() != B.size()) {
            A.add(num);
            B.add(A.poll());
        } else {
            B.add(num);
            A.add(B.poll());
        }
    }
    public double findMedian() {
        return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;
    }
}

